class ListNode {
    /**
     * 构建单向链表
     * data:节点数据
     * next:链表下一个节点
     * ListNode:链表节点结构
     */
    int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
    }

    public ListNode() {
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

}

class SingleLinkedList{
    private ListNode headnode = new ListNode(0);
    /**
     * 遍历链表，返回单向链表长度
     * @param headNode：链表头结点
     * @return length: 链表长度
     */
    int ListLength(ListNode headNode){
        int length = 0;
        ListNode currentNode = headNode;
        while(currentNode!= null){
            length++;
            currentNode = currentNode.getNext();
        }
        return length;
    }


    /**
     * 在链表中插入节点
     * @param headNode:链表头结点
     * @param nodeToInsert:插入节点
     * @param position:相对于头结点的当前位置
     * @return: 返回头结点
     */
    ListNode InsertLinkedList(ListNode headNode, ListNode nodeToInsert, int position){
        //链表为空时，插入头结点
        if(headNode == null){
            return nodeToInsert;
        }
        int size = ListLength(headNode);
        if(position < 1 || position > size+1){
            System.out.println("输入不合法");
            return headNode;
        }

        if(position == 1){
            //链表开头插入
            nodeToInsert.setNext(headNode);
            return headNode;
        }
        else{
            //链表中间或末尾插入节点数据
            ListNode previousNode = headNode;
            int count = 1;
            while(count < position - 1){
                previousNode = previousNode.getNext();
                count++;
            }
            ListNode currentNode = previousNode.getNext();
            nodeToInsert.setNext(currentNode);
            previousNode.setNext(nodeToInsert);
        }
        return headNode;
    }

    /**
     * 删除链表中某一节点
     * @param headNode:链表头节点
     * @param position:相对于头结点当前位置
     * @return headNode 返回头节点
     */
    ListNode DeleteNodeFromLinkedList(ListNode headNode, int position){
        int size = ListLength(headNode);
        if(position > size || position < 0){
            System.out.println("输入不合法");
            return headNode;
        }

        if(position == 1){
            //删除头结点
            ListNode currentNode = headNode.getNext();
            currentNode = null;
            return currentNode;
        }
        else {
            ListNode previousNode = headNode;
            int count = 1;
            while (count < position) {
                previousNode = previousNode.getNext();
                count++;
            }
            ListNode currentNode = previousNode.getNext();
            previousNode.setNext(currentNode.getNext());
            currentNode = null;
        }
        return headNode;
    }

    /**
     * 初始化
     * 传入的节点头节点，这里我们创建的链表是带头结点的，
     * 头结点不带信息，方便与链表操作
     * @param headNode:头结点
     * @return 头结点
     */
    public ListNode initLink(ListNode headNode) {  //初始化节点
        headNode = new ListNode();
        headNode.setNext(null);
        return headNode;
    }

    /**
     * 打印链表
     */
    public void printList() {
        if(headnode.next == null){
            System.out.println("链表为空");
            return;
        }

        ListNode node = headnode.next;
        while(node != null) {
            System.out.println(node.getData());
            node = node.getNext();
        }
    }

    /**
     * 添加链表元素
     * @param headNode:头结点
     */
    public void addList(ListNode headNode){
        ListNode temp = headnode;
        while (true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = headNode;
    }
}

class ListNodeTest {
    public static void main(String[] args) {
        ListNode firstNode = new ListNode(1);
        ListNode secondNode = new ListNode(2);
        ListNode thirdNode = new ListNode(3);
        ListNode fourthNode = new ListNode(4);

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addList(firstNode);
        singleLinkedList.addList(secondNode);
        singleLinkedList.addList(thirdNode);

        System.out.println("插入之前的单向链表序列:");
        singleLinkedList.printList();

        singleLinkedList.InsertLinkedList(firstNode,fourthNode,3);

        System.out.println("插入之后的单向链表序列:");
        singleLinkedList.printList();

    }
}



